import java.io.*;
import java.util.*;

public class CityDB {
	private static class City implements StateWithHeuristic {
		public String name;
		public double latitude;
		public double longitude;
		public ArrayList<City> neighbors;
		
		public City() {
			neighbors = new ArrayList<>();
		}
		
		public City(String name, double latitude, double longitude) {
			this();
			this.name = name;
			this.latitude = latitude;
			this.longitude= longitude;
		}

		public double distanceTo(City other) {
			double deltaLat = Math.toRadians(latitude - other.latitude);
			double deltaLong = Math.toRadians(longitude - other.longitude);
			double dr = Math.pow(Math.sin(deltaLat / 2), 2) + Math.pow(Math.sin(deltaLong / 2), 2) * Math.cos(Math.toRadians(latitude)) * Math.cos(Math.toRadians(other.latitude));
			return 3958.76 * 2 * Math.atan2(Math.sqrt(dr), Math.sqrt(1 - dr));
		}

		public String toString() {
			return name;
		}

		public boolean equals(Object obj) {
			if (!(obj instanceof City))
				return false;
			if (obj == this)
				return true;
			return name.equals(((City)obj).name);
		}

		public int hashCode() {
			return name.hashCode();
		}

		public Map<StateWithHeuristic, Double> getNeighborsWithCost() {
			Map<StateWithHeuristic,Double> neighbors = new HashMap<>();
			
			for (City city : this.neighbors)
				neighbors.put(city, distanceTo(city));
			
			return neighbors;
		}

		public double getEstimatedCostToGoal(StateWithHeuristic goal) {
			if (!(goal instanceof City))
				throw new IllegalArgumentException();

			return distanceTo((City)goal);
		}
	}

	private Map<String,City> nameToCity;
	
	/**
	 * Initializes a new <code>CityDB</code> object with city information
	 * loaded from the file <tt>CityInfo.txt</tt>.
	 * 
	 * @throws IOException If the file <tt>CityInfo.txt</tt> cannot be found
	 * or an I/O error occurs during processing of the file.
	 */
	public CityDB() throws IOException {
		this("CityInfo.txt");
	}

	/**
	 * Initializes a new <code>CityDB</code> object with city information
	 * loaded from the specified file.
	 * 
	 * @param filename The name of the file from which to load city information.
	 * @throws IOException If the file <tt>CityInfo.txt</tt> cannot be found
	 * or an I/O error occurs during processing of the file.
	 */
	public CityDB(String filename) throws IOException {
		nameToCity = new HashMap<>();
		load(filename);
	}
	
	/**
	 * Returns the <code>StateWithHeuristic</code> object representing the
	 * specified city, or <code>null</code> if no information about the
	 * specified city is available.
	 *  
	 * @param name The city name in "&lt;<i>city</i>&gt;, &lt;<i>state</i>&gt;"
	 * format, where &lt;<i>state</i>&gt is a two-letter state abbreviation.
	 * Names are case sensitive.
	 * @return the <code>StateWithHeuristic</code> object representing the
	 * specified city, or <code>null</code> if no information about the
	 * specified city is available.
	 * @see {@link getCityNames getCityNames()}
	 */
	public City get(String name) {
		return nameToCity.get(name);
	}
	
	/**
	 * Returns a collection of the names of all available cities in this
	 * <code>CityDB</code>. 
	 * 
	 * @return a collection of the names of all available cities in this
	 * <code>CityDB</code>.
	 */
	public Collection<String> getCityNames() {
		return Collections.unmodifiableSet(nameToCity.keySet());
	}
	
	private void load(String filename) throws IOException {
		ArrayList<City> cities = new ArrayList<>();
		BufferedReader in = new BufferedReader(new FileReader(filename));
		String line;
		Scanner sc;
		while (true) {
			line = in.readLine();
			sc = new Scanner(line);
			sc.useDelimiter("\t");
			if (sc.hasNextInt())
				break;
			City city = new City(sc.next(), sc.nextDouble(), sc.nextDouble());
			cities.add(city);
			nameToCity.put(city.name, city);
		}
		for (int i = 0; i < cities.size(); i++) {
			while (sc.hasNextInt()) {
				int neighborIndex = sc.nextInt();
				cities.get(i).neighbors.add(cities.get(neighborIndex));
				cities.get(neighborIndex).neighbors.add(cities.get(i));
			}
			line = in.readLine();
			if (line == null)
				break;
			sc = new Scanner(line);
			sc.useDelimiter("\t");
		}
		in.close();
	}
}
